package personal.leil.learning.reverse;

import personal.leil.learning.DNode;
import personal.leil.learning.utils.LinkedListUtils;

/**
 * 反转一个双链表
 * <p>
 * 反转一个双链表代码实现
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-5
 */
public class ReverseDoubleLinkedList {

    /**
     * reverse double linked list
     *
     * @param head Head node for double linked list
     * @return Head node for reverse linked list
     */
    public static DNode reverse(DNode head) {
        DNode prev = null;
        DNode current = head;
        while (current != null) {
            DNode next = current.getNext();
            prev = current.getPrev();
            current.setPrev(next);
            current.setNext(prev);
            // prev、current指针右移
            prev = current;
            current = next;
        }
        return prev;
    }


    /********************* For Test *************************/

    public static DNode buildDoubleLinkedList() {
        DNode head = new DNode(0);
        // add one node
        DNode n1 = new DNode(1);
        head.setNext(n1);
        n1.setPrev(head);

        DNode n2 = new DNode(2);
        n1.setNext(n2);
        n2.setPrev(n1);

        DNode n3 = new DNode(3);
        n2.setNext(n3);
        n3.setPrev(n2);

        DNode n4 = new DNode(4);
        n3.setNext(n4);
        n4.setPrev(n3);

        return head;
    }

    public static void main(String[] args) {
        DNode head = buildDoubleLinkedList();
        System.out.println("before reverse:");
        LinkedListUtils.printDoubleLinkedList(head);

        DNode headAfterReverse = reverse(head);
        System.out.println("after reverse:");
        LinkedListUtils.printDoubleLinkedList(headAfterReverse);
    }

}
